package leetcode.code1091;

import java.util.Stack;

import leetcode.helper.HelpDebug;

public class Solution1 extends Solution1091 {

	private int x;
	private int y;

	@Override
	public int shortestPathBinaryMatrix(int[][] grid) {
		if (grid == null || grid[0][0] == 1)
			return -1;
		x = grid.length;
		y = grid[0].length;
		if (grid[x - 1][y - 1] == 1)
			return -1;
		grid[0][0] = 1;
		Stack<int[]> s = new Stack<>();
		s.add(new int[] { 0, 0 });
		while (s.size() > 0) {
			int[] now = s.pop();
			int a = now[0];
			int b = now[1];
			int next = grid[a][b] + 1;
			this.update(grid, a - 1, b - 1, next, s);
			this.update(grid, a - 1, b, next, s);
			this.update(grid, a, b - 1, next, s);
			this.update(grid, a + 1, b - 1, next, s);
			this.update(grid, a - 1, b + 1, next, s);
			this.update(grid, a + 1, b, next, s);
			this.update(grid, a, b + 1, next, s);
			this.update(grid, a + 1, b + 1, next, s);
		}
		HelpDebug.printObject(grid);
		return grid[x - 1][y - 1] == 0 ? -1 : grid[x - 1][y - 1];// 结尾被1环绕了
	}

	private void update(int[][] grid, int a, int b, int next, Stack<int[]> s) {
		if (a >= 0 && a < x && b >= 0 && b < y && (grid[a][b] == 0 || grid[a][b] > next)) {
			grid[a][b] = next;
			s.add(new int[] { a, b });
		}
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		String s = "[[0,0,0,0,1,1],[0,1,0,0,1,0],[1,1,0,1,0,0],[0,1,0,0,1,1],[0,1,0,0,0,1],[0,0,1,0,0,0]]";
		HelpDebug.printObject(HelpDebug.str2array1(s));
	}

}
